package top.hkyzf.study.leetcode.graph;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 朱峰
 * @date 2022-1-29 10:05
 */
public class 地图中的最高点_1765 {
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length;
        int n = isWater[0].length;
        boolean[][] watch = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    isWater[i][j] = 0;
                    queue.offer(new int[]{i, j});
                    watch[i][j] = true;
                }
            }
        }
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        while (!queue.isEmpty()) {
            int[] ints = queue.poll();
            for (int i = 0; i < 4; i++) {
                int newX = ints[0] + dx[i];
                int newY = ints[1] + dy[i];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && !watch[newX][newY]) {
                    watch[newX][newY] = true;
                    queue.offer(new int[]{newX, newY});
                    isWater[newX][newY] = isWater[ints[0]][ints[1]] + 1;
                }
            }
        }
        return isWater;
    }

    @Test
    public void testIsWater () {
        int[][] isWater = {{0,0,1,1},{1,0,0,1},{0,0,0,0}};
        int[][] ints = highestPeak(isWater);
        for (int[] i : ints) {
            System.out.println(Arrays.toString(i));
        }
    }
}
